home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / ai / netstuff / ham.c < prev    next >
C/C++ Source or Header  |  1987-10-05  |  7KB  |  335 lines
  1. /* ham.c
  2.  * c version of the hamming net
  3.  * david leasure
  4.  * 9/25/87
  5.  *
  6.  * this routine is a hamming classification network
  7.  * described in IEEE ASSP April 1987 by Richard P. Lippmann pg. 9
  8.  * correcting for a presumed bug in the presented routine
  9.  * the bug is the value set for THETA by Lippmann. When THETA is
  10.  * N / 2 it so overwhelms the outputs from the lower net that only 0
  11.  * activation values are passed up from the threshold function.
  12.  * I have chosen to set epsilon to 1 / 2M and to not have an upper
  13.  * limit on the threshold function so no saturation occurs
  14.  *
  15.  * the program is somewhat inefficient because of the use of
  16.  * data storage for maxnet (t[k,l] in lippman's) and for output[t,M]
  17.  * but they could be useful in a simulator of this network which allowed
  18.  * things to be fiddled with.
  19.  * the code could be improved by not encoding the size and values
  20.  * of the node matrices directly, too, reading them instead from files
  21.  * and/or a user interface.
  22.  *
  23.  * if you improve the code, please send me the diff's
  24.  * david e. leasure
  25.  * ihnp4!homxc!del or del@homxc.att.com
  26.  */
  27.  
  28. /* EMACS_MODES: tabstop=4 c */
  29.  
  30. #include <stdio.h>
  31. #include <ctype.h>
  32.  
  33. /* number of bits per exemplar (7x5) */
  34. #define N 35
  35.  
  36. /*number of exemplars */
  37. #define M 10
  38.  
  39. /* presentation (r,c) */
  40. #define rows 7
  41. #define cols 5
  42.  
  43. /* define maximum number of iterations before convergence */
  44. #define MAX_ITERATION 20
  45.  
  46. /* define the exemplary training data */
  47. /* should be replaced later with a read routine */
  48.  
  49. static int exemplars[M][N] = {
  50. /* 0 */
  51. -1,1,1,1,-1,
  52. 1,-1,-1,-1,1,
  53. 1,-1,-1,-1,1,
  54. 1,-1,-1,-1,1,
  55. 1,-1,-1,-1,1,
  56. 1,-1,-1,-1,1,
  57. -1,1,1,1,-1,
  58. /* 1 */
  59. -1,-1,-1,-1,1,
  60. -1,-1,-1,1,1,
  61. -1,-1,-1,-1,1,
  62. -1,-1,-1,-1,1,
  63. -1,-1,-1,-1,1,
  64. -1,-1,-1,-1,1,
  65. -1,-1,-1,-1,1,
  66. /* 2 */
  67. -1,1,1,1,-1,
  68. 1,-1,-1,-1,1,
  69. -1,-1,-1,-1,1,
  70. -1,-1,-1,1,-1,
  71. -1,-1,1,-1,-1,
  72. -1,1,-1,-1,-1,
  73. 1,1,1,1,1,
  74. /* 3 */
  75. 1,1,1,1,1,
  76. -1,-1,-1,1,-1,
  77. -1,-1,1,-1,-1,
  78. -1,1,1,1,-1,
  79. -1,-1,-1,-1,1,
  80. 1,-1,-1,-1,1,
  81. -1,1,1,1,-1,
  82. /* 4 */
  83. -1,-1,-1,1,-1,
  84. -1,-1,1,1,-1,
  85. -1,1,-1,1,-1,
  86. 1,-1,-1,1,-1,
  87. 1,1,1,1,1,
  88. -1,-1,-1,1,-1,
  89. -1,-1,-1,1,-1,
  90. /* 5 */
  91. 1,1,1,1,1,
  92. 1,-1,-1,-1,-1,
  93. 1,1,1,1,-1,
  94. -1,-1,-1,-1,1,
  95. -1,-1,-1,-1,1,
  96. 1,-1,-1,-1,1,
  97. -1,1,1,1,-1,
  98. /* 6 */
  99. -1,-1,1,1,-1,
  100. -1,1,-1,-1,-1,
  101. 1,-1,-1,-1,-1,
  102. 1,1,1,1,-1,
  103. 1,-1,-1,-1,1,
  104. 1,-1,-1,-1,1,
  105. -1,1,1,1,-1,
  106. /* 7 */
  107. 1,1,1,1,1,
  108. -1,-1,-1,-1,1,
  109. -1,-1,-1,1,-1,
  110. -1,-1,-1,1,-1,
  111. -1,-1,1,-1,-1,
  112. -1,-1,1,-1,-1,
  113. -1,-1,1,-1,-1,
  114. /* 8 */
  115. -1,1,1,1,-1,
  116. 1,-1,-1,-1,1,
  117. 1,-1,-1,-1,1,
  118. -1,1,1,1,-1,
  119. 1,-1,-1,-1,1,
  120. 1,-1,-1,-1,1,
  121. -1,1,1,1,-1,
  122. /* 9 */
  123. -1,1,1,1,-1,
  124. 1,-1,-1,-1,1,
  125. 1,-1,-1,-1,1,
  126. -1,1,1,1,1,
  127. -1,-1,-1,-1,1,
  128. -1,-1,-1,1,-1,
  129. -1,1,1,-1,-1};
  130.  
  131. static float w[N][M];           /* weights of lower subnet */
  132. static float maxnet[M][M];      /* weights of maxnet */
  133. /* input pattern */
  134. static int x[N] =
  135.     {/* altered 5 with 4 flipped bits */
  136.     /* 9 */
  137.     -1,-1,1,1,-1,
  138.     -1,-1,-1,1,1,
  139.     1,-1,1,-1,1,
  140.     1,1,-1,1,-1,
  141.     -1,-1,-1,1,-1,
  142.     -1,-1,1,1,-1,
  143.     1,1,1,-1,-1};
  144.  
  145. /* input vector */
  146. static output[MAX_ITERATION][M]; /* output at time t matrix */
  147.  
  148. #define THETA  0.0 /* N / 2.0 */
  149. #define EPSILON 1.0 / (2.0 * M)
  150.  
  151. /* INIT_LOWER 
  152.  * initialize the weight matrix for the lower network
  153.  */
  154. int init_lower()
  155. {
  156.     int i, j;
  157.  
  158.     for (i=0; i<N; i++) {
  159.         for (j=0; j<M; j++) {
  160.             w[i][j] = exemplars[j][i]/2.0;
  161.         }
  162.     }
  163. }
  164.  
  165. /* INIT_UPPER
  166.  * init the weight matrix for the upper maxnet
  167.  */
  168. int init_upper()
  169. {
  170.     int k, l;
  171.  
  172.     for (k=0; k<M; k++) {
  173.         for (l=0; l<M; l++) {
  174.             if (k==l)
  175.                 maxnet[k][l] = 1.0;
  176.             else
  177.                 maxnet[k][l] =  -1.0 / 20.0;
  178.         }
  179.     }
  180. }
  181.  
  182.  
  183. /* INIT_SUM 
  184.  * the code to perform the summation of the weight/input value products
  185.  * for each output, i.e. (sum(i=0..N-1) w[i][j]*x[i]) - THETA
  186. */
  187. float init_sum(j)
  188.     int j;
  189. {
  190.     int i;
  191.     float sum;
  192.  
  193.     sum = 0;
  194.     for (i=0; i<N; i++) {
  195.         sum = sum + (w[i][j] * x[i]);
  196.     }
  197.     return(sum - THETA);
  198. }
  199.  
  200. /* CONVERGE_SUM(J,T)
  201.  * perform the sum for the maxnet output calculation
  202.  * i.e., output[j](t) - epsilon * sum(k<>j where j,k=0..M)output[k](t)
  203.  */
  204. float converge_sum(j,t)
  205.     int j,t;
  206. {
  207.     int k, sum;
  208.  
  209.     sum = 0;
  210.     for (k=0; k<M; k++)
  211.         if (k != j)     sum = sum + output[t][k];
  212.     sum = output[t][j] - EPSILON * sum;
  213.     return(sum);
  214. }
  215.  
  216. /* F_THRESH(ALPHA)
  217.  * implement a simple threshold logic nonlinearity
  218.  * I have chosen not to give it a saturation cutoff
  219.  */
  220. float f_thresh(alpha)
  221.     float alpha;
  222. {
  223.     if (alpha <= 0.0)
  224.         return(0.0);
  225.     else
  226.         return(alpha);
  227. }
  228.  
  229. /* INIT_UNKNOWN()
  230.  * apply the input to the lower net and derive state 0 of the maxnet
  231.  */
  232. int init_unknown()
  233. {
  234.     int j;
  235.  
  236.     for (j=0; j<M; j++) {
  237.         output[0][j] = f_thresh(init_sum(j));
  238.     }
  239. }
  240.  
  241. /* CONVERGE()
  242.  * perform up to MAX_ITERATIONs of the convergence function
  243.  * answer found when only one of the maxnet outputs is high
  244.  * that output indexes the exemplars for the correct pattern
  245.  */
  246. int converge()
  247. {
  248.     int t, count, j, winner;
  249.  
  250.     count = 2; /* prime the pump */
  251.     winner = -1; /* start with "no winner" */
  252.  
  253.     for (t=1; t<MAX_ITERATION && count>1; t++) {
  254.         count = 0;
  255.         for (j=0; j<M; j++) {
  256.             if ((output[t][j] = f_thresh(converge_sum(j,t - 1))) > 0) {
  257.                 winner = j;
  258.                 count++;
  259.             }
  260.         }
  261.     }
  262.     if (count != 1)
  263.         winner = -1; /* error condition not supposed to occur */
  264.     return(winner);
  265. }
  266.  
  267. /* SHOW_EXEMPLAR(EX)
  268.  * print the exemplar(ex) using .'s for -1 and *'s for +1
  269.  * break the lines so the pattern is correctly seen
  270.  */
  271. int show_exemplar(ex)
  272.     int ex[];
  273. {
  274.     int c, i;
  275.  
  276.     c = 0;
  277.     for (i=0; i<N; i++) {
  278.         if (ex[i] < 0) {
  279.             printf(".");
  280.         }
  281.         else {
  282.             printf("*");
  283.         }
  284.         if (++c == cols) {
  285.             printf("\n");
  286.             c = 0;
  287.         }
  288.     }
  289.     printf("\n");
  290. }
  291.  
  292. /* SHOW_EXEMPLARS()
  293.  * show all the exemplars
  294.  */
  295. int show_exemplars()
  296. {
  297.     int j;
  298.  
  299.  
  300.     for (j=0; j<M; j++) {
  301.         printf("Exemplar %d:\n",j);
  302.         show_exemplar(&exemplars[j][0]);
  303.     }
  304.     printf("\n");
  305. }
  306.  
  307.  
  308. main()
  309. {
  310.     int winner;
  311.  
  312.     printf("Hamming Neural Net Example\n\n");
  313.  
  314.     /*
  315.     show_exemplars(); 
  316.     */
  317.  
  318.     init_lower();    
  319.     init_upper();   
  320.     init_unknown();
  321.     winner = converge();
  322.     if (winner >= 0) {
  323.         printf("The winner is %d.\n", winner);
  324.         printf("\nInput pattern:\n");
  325.         show_exemplar(&x[0]);
  326.         printf("\n\nExemplar:\n");
  327.         show_exemplar(&exemplars[winner][0]);
  328.         printf("\n");
  329.     }
  330.     else { /* according to lippmann, this should never happen */
  331.         printf("Something's wrong. No winner.\n");
  332.     }
  333.     exit(0);
  334. }
  335.